<!doctype html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>



<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />















  
  
  <link href="/pages/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/pages/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/pages/css/main.css?v=5.1.0" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="算法,时间复杂度," />








  <link rel="shortcut icon" type="image/x-icon" href="/pages/favicon.ico?v=5.1.0" />






<meta name="description" content="在前面的blog中均使用了类似于$\theta (n^2)$或是$\theta (n \log n)$等字样来书写算法的时间复杂度，用于衡量一个算法的效率。在这个blog中会对时间复杂度作出详细的介绍。">
<meta name="keywords" content="算法,时间复杂度">
<meta property="og:type" content="article">
<meta property="og:title" content="算法效率——时间复杂度">
<meta property="og:url" content="http://ly0111.oschina.io/pages/2017/04/19/算导笔记/时间复杂度/index/index.html">
<meta property="og:site_name" content="JROier's Blog">
<meta property="og:description" content="在前面的blog中均使用了类似于$\theta (n^2)$或是$\theta (n \log n)$等字样来书写算法的时间复杂度，用于衡量一个算法的效率。在这个blog中会对时间复杂度作出详细的介绍。">
<meta property="og:image" content="http://ly0111.oschina.io/pages/img/TimeComplexity.png">
<meta property="og:updated_time" content="2017-04-20T14:18:42.288Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="算法效率——时间复杂度">
<meta name="twitter:description" content="在前面的blog中均使用了类似于$\theta (n^2)$或是$\theta (n \log n)$等字样来书写算法的时间复杂度，用于衡量一个算法的效率。在这个blog中会对时间复杂度作出详细的介绍。">
<meta name="twitter:image" content="http://ly0111.oschina.io/pages/img/TimeComplexity.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/pages/',
    scheme: 'Pisces',
    sidebar: {"position":"right","display":"post","offset":12,"offset_float":0,"b2t":false,"scrollpercent":false},
    fancybox: true,
    motion: true,
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"�����ؼ���","hits_empty":"û��������: ${query}","hits_stats":"${hits} �����ؼ�¼����ʱ ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://ly0111.oschina.io/pages/2017/04/19/算导笔记/时间复杂度/index/"/>





  <title> 算法效率——时间复杂度 | JROier's Blog </title>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  














  
  
    
  

  <div class="container sidebar-position-right page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/pages/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">JROier's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/pages/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i><br/>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/pages/categories" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i><br/>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/pages/archives" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i><br/>
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/pages/tags" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i><br/>
            
            标签
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocapitalize="off" autocomplete="off" autocorrect="off"
             placeholder="搜索..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>


 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
    <link itemprop="mainEntityOfPage" href="http://ly0111.oschina.io/pages/pages/2017/04/19/算导笔记/时间复杂度/index/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="JROier">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/pages/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JROier's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
            
            
              
                算法效率——时间复杂度
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-04-19T18:33:42+08:00">
                2017-04-19
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/pages/categories/《算法导论》笔记/" itemprop="url" rel="index">
                    <span itemprop="name">《算法导论》笔记</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    


    <div class="post-body" itemprop="articleBody">

      
      

      
        <p><strong>在前面的blog中均使用了类似于$\theta (n^2)$或是$\theta (n \log n)$等字样来书写算法的时间复杂度，用于衡量一个算法的效率。在这个blog中会对时间复杂度作出详细的介绍。</strong></p>
<a id="more"></a>
<h1 id="什么是时间复杂度"><a href="#什么是时间复杂度" class="headerlink" title="什么是时间复杂度"></a>什么是时间复杂度</h1><p>当算法的输入规模<strong>足够大</strong>，使得<strong>只有运行时间的增长量级有关</strong>时，我们研究算法的<strong>渐进</strong>效率。即当输入规模无限增加时，<strong>在极限中</strong>，算法的运行时间如何随着输入规模的变大而增加。而用于<strong>定量</strong>描述这样一个变化的函数便是时间复杂度。</p>
<h1 id="渐进记号"><a href="#渐进记号" class="headerlink" title="渐进记号"></a>渐进记号</h1><p>用来描述算法渐进运行时间的记号根据定义域为自然数集$N$的函数来定义。这样的记号对描述<strong>最坏运行时间</strong>函数$T(n)$是方便的，因为该函数通常只定义在整数输入规模上。然而有时我们不仅仅对算法的最坏运行情况感兴趣，我们希望刻画<strong>任何输入</strong>的运行时间，因而便有了用于刻画任何输入的运行时间的渐进记号。<br><img src="/pages/img/TimeComplexity.png" alt=""></p>
<h2 id="theta-记号"><a href="#theta-记号" class="headerlink" title="$\theta$记号"></a>$\theta$记号</h2><p>在插入排序那个blog中，写出了其最坏情况运行时间为$T(n)=\theta (n^2)$，在这里会给出$\theta$记号的确切定义。</p>
<h3 id="theta-记号的定义"><a href="#theta-记号的定义" class="headerlink" title="$\theta$记号的定义"></a>$\theta$记号的定义</h3><p><strong>对于一个给定的函数$g(n)$，用$\theta (g(n))$来表示以下函数的集合：<br>$\theta (g(n))= \{f(n):\exists正常量c_1 、c_2 、 n_0，\forall n\geq n_0，有0\leq c_1 g(n) \leq f(n) \leq c_2 g(n)\}$</strong></p>
<h3 id="theta-记号的使用"><a href="#theta-记号的使用" class="headerlink" title="$\theta$记号的使用"></a>$\theta$记号的使用</h3><p>若存在正常量$c_1$和$c_2$，使得对于足够大的$n$，函数$f(n)$能“夹入”$c_1 g(n)$和$c_2 g(n)$之间，则$f(n)$属于集合$\theta (g(n))$，即$f(n)\in \theta (g(n))$，通常我们用$f(n)=\theta (g(n))$表达相同的概念。</p>
<h3 id="theta-记号的几何意义"><a href="#theta-记号的几何意义" class="headerlink" title="$\theta$记号的几何意义"></a>$\theta$记号的几何意义</h3><p>上图给出了函数$f(n)$与$g(n)$的一幅直观画面，其中$f(n)=\theta (g(n))$。<strong>对在$n_0$及其右边的所有值，$f(n)$的值位于或高于$c_1 g(n)$且位于或低于$c_2 g(n)$。</strong>即$\forall n\geq n_0$，函数$f(n)$在一个常量因子内等于$g(n)$。我们称$g(n)$是$f(n)$的一个<strong>渐近紧确界</strong></p>
<h3 id="渐近非负"><a href="#渐近非负" class="headerlink" title="渐近非负"></a>渐近非负</h3><p>$\theta (g(n))$的定义要求每个成员$f(n)\in \theta (g(n))$均为<strong>渐近非负</strong>，即当n足够大时，$f(n)$非负。（<strong>渐近正函数</strong>就是对所有足够大的$n$均为正的函数。）因此，函数$g(n)$本身也必为渐近非负，否则集合$\theta (g(n))$为空。所以我们假设用在$\theta$记号中的每个函数均为渐近非负</p>
<h3 id="theta-记号的非形式化概念"><a href="#theta-记号的非形式化概念" class="headerlink" title="$\theta$记号的非形式化概念"></a>$\theta$记号的非形式化概念</h3><p>$\theta$记号相当于扔掉低阶项并忽略最高阶项前的系数，例如$\frac{1}{2}n^2-3n=\theta (n^2)$，$6n^3 \ne \theta (n^2)$。<strong>一般来说，对任意多项式$p(n)=\sum^d_{i=0} a_i n^i$，其中$a_i$为常量且$a_d&gt;0$，则有$p(n)=\theta (n^d)$</strong>。</p>
<h2 id="O-记号"><a href="#O-记号" class="headerlink" title="$O$记号"></a>$O$记号</h2><p>$\theta$记号渐近地给出一个函数的上界和下界。当只有一个<strong>渐进上界</strong>时，使用$O$记号。</p>
<h3 id="O-记号的定义"><a href="#O-记号的定义" class="headerlink" title="$O$记号的定义"></a>$O$记号的定义</h3><p><strong>对于给定的函数$g(n)$，用$O(g(n))$(读作“大$Og(n)$”，有时仅读作“$Og(n)$”)来表示以下函数的集合：<br>$O(g(n))= \{f(n):\exists正常量c、 n_0，\forall n\geq n_0，有0\leq f(n) \leq c g(n)\}$</strong></p>
<h3 id="O-记号的使用"><a href="#O-记号的使用" class="headerlink" title="$O$记号的使用"></a>$O$记号的使用</h3><p>对在$n_0$及其右边的所有值$n$，函数$f(n)$的值总小于或等于$cg(n)$，我们记$f(n)=O(g(n))$以指出函数$f(n)$是集合$O(g(n))$的成员。<strong>$f(n)=\theta (g(n))$蕴含着$f(n)=O(g(n))$，因为$\theta$记号是一个比$O$记号更强的概念。按集合论中的写法，则有$\theta (g(n)) \subseteq O(g(n))$。</strong></p>
<h3 id="O-记号的几何意义"><a href="#O-记号的几何意义" class="headerlink" title="$O$记号的几何意义"></a>$O$记号的几何意义</h3><p>类似$\theta$记号，<strong>对在$n_0$及其右边的所有值，$f(n)$的值位于或低于$cg(n)$。</strong></p>
<h3 id="O-记号的非形式化概念"><a href="#O-记号的非形式化概念" class="headerlink" title="$O$记号的非形式化概念"></a>$O$记号的非形式化概念</h3><p>类似$\theta$记号，不再赘述。<strong>$O$记号所给出的渐近上界不一定是渐进上确界，例如线性函数an+b在$O(n)$中，也在$O(n^2)$中，但是不在$\theta (n^2)$中，可以很容易地证明这个结论。</strong></p>
<h2 id="Omega-记号"><a href="#Omega-记号" class="headerlink" title="$\Omega$记号"></a>$\Omega$记号</h2><p>$O$记号提供了一个函数的渐近上界，$\Omega$记号提供了渐近下界。</p>
<h3 id="Omega-记号的定义"><a href="#Omega-记号的定义" class="headerlink" title="$\Omega$记号的定义"></a>$\Omega$记号的定义</h3><p><strong>对于给定的函数$g(n)$，用$\Omega(g(n))$(读作“大$\Omega g(n)$”，有时仅读作“$\Omega g(n)$”)来表示以下函数的集合：<br>$\Omega(g(n))= \{f(n):\exists正常量c、 n_0，\forall n\geq n_0，有0\leq c g(n) \leq f(n)\}$</strong></p>
<h3 id="Omega-记号的使用"><a href="#Omega-记号的使用" class="headerlink" title="$\Omega$记号的使用"></a>$\Omega$记号的使用</h3><p>对在$n_0$及其右边的所有值$n$，函数$f(n)$的值总大于或等于$cg(n)$，我们记$f(n)=\Omega(g(n))$以指出函数$f(n)$是集合$\Omega(g(n))$的成员。<strong>对任意两个函数$f(n)$及$g(n)$，有$f(n)=\theta (g(n))$，当且仅当$f(n)=O(g(n))$且$f(n)=\Omega(g(n))$。</strong></p>
<h3 id="Omega-记号的几何意义"><a href="#Omega-记号的几何意义" class="headerlink" title="$\Omega$记号的几何意义"></a>$\Omega$记号的几何意义</h3><p><strong>对在$n_0$及其右边的所有值，$f(n)$的值位于或高于$cg(n)$。</strong></p>
<h2 id="o-记号"><a href="#o-记号" class="headerlink" title="$o$记号"></a>$o$记号</h2><p>由$O$记号提供的渐进上界可能不是渐近紧确的。我们使用$o$记号来表示一个非渐近紧确的上界。</p>
<h3 id="o-记号的定义"><a href="#o-记号的定义" class="headerlink" title="$o$记号的定义"></a>$o$记号的定义</h3><p><strong>对于给定的函数$g(n)$，用$o(g(n))$(读作“小$og(n)$”)来表示以下函数的集合：<br>$o(g(n))= \{f(n):\forall 正常量c&gt;0，\exists n_0&gt;0，\forall n\geq n_0，有0\leq f(n) &lt; c g(n)\}$</strong></p>
<h3 id="o-记号的意义"><a href="#o-记号的意义" class="headerlink" title="$o$记号的意义"></a>$o$记号的意义</h3><p>若$f(n)=o(g(n))$，则$\lim\limits_{n \to \infty} \frac{f(n)}{g(n)} =0$。</p>
<h2 id="omega-记号"><a href="#omega-记号" class="headerlink" title="$\omega$记号"></a>$\omega$记号</h2><p>$\omega$记号与$\Omega$记号的关系类似于$O$记号与$o$记号的关系。我们使用$\omega$记号来表示一个非渐近紧确的下界。</p>
<h3 id="omega-记号的定义"><a href="#omega-记号的定义" class="headerlink" title="$\omega$记号的定义"></a>$\omega$记号的定义</h3><p><strong>方式一：$f(n)\in\omega (g(n))当且仅当g(n)\in o(f(n))$</strong><br><strong>方式二：</strong><br>$\omega(g(n))= \{f(n):\forall 正常量c&gt;0，\exists n_0&gt;0，\forall n\geq n_0，有0\leq cg(n) &lt; f(n)\}$<br>例如，$\frac{n^2}{2} \in \omega(n)$，但是$\frac{n^2}{2} \notin \omega(n^2)$。</p>
<h3 id="omega-记号的意义"><a href="#omega-记号的意义" class="headerlink" title="$\omega$记号的意义"></a>$\omega$记号的意义</h3><p>关系$f(n)=\omega (g(n))$蕴含着$\lim\limits_{n \to \infty} \frac{f(n)}{g(n)}=\infty$，也就是说，如果这个极限存在，那么当n趋近于无穷时，$f(n)$是$g(n)$的任意大。</p>
<h1 id="等式及不等式中的渐进记号"><a href="#等式及不等式中的渐进记号" class="headerlink" title="等式及不等式中的渐进记号"></a>等式及不等式中的渐进记号</h1><p>当渐进记号<strong>独立于</strong>等式（或不等式）的右边（即不在一个更大的公式内）时，如在$n=O(n^2)$中，我们已经定义了等号意指集合的成员关系：$n\in O(n^2)$。然而，一般来说，当渐进记号<strong>出现在某个公式中</strong>时，我们将其解释为代表某个我们不关注名称的<strong>匿名函数</strong>。例如，公式$2n^2+3n+1=2n^2+\theta (n)$意指$2n^2+3n+1=2n^2+f(n)$，其中$f(n)=\theta (n)$，如$f(n)=2n+1$。<br>在某些例子中，渐进记号出现在等式的左边，例如$2n^2+\theta (n)=\theta (n^2)$<br>我们使用以下规则来解释这种等式：<strong>无论怎样选择等号左边的匿名函数，总有一种办法来选择等号右边的匿名函数使等式成立。</strong>因此，我们的例子意指对<strong>任意</strong>函数$f(n)\in \theta (n)$，存在<strong>某个</strong>函数$g(n)\in \theta (n^2)$，使得对所有的$n$，有$2n^2+f(n)=g(n)$。换句话说，等式右边比左边提供的细节更粗糙。<br>我们可以将许多这样的关系连在一起，例如：<br>$$2n^2+3n+1=2n^2+\theta (n)=\theta (n^2)$$</p>
<h1 id="比较各种函数"><a href="#比较各种函数" class="headerlink" title="比较各种函数"></a>比较各种函数</h1><p>实数的许多关系性质也适用于渐近比较。下面假定$f(n)$和$g(n)$渐近为正。</p>
<h2 id="传递性"><a href="#传递性" class="headerlink" title="传递性"></a>传递性</h2><p>$$f(n)=\theta(g(n))且g(n)=\theta(h(n))，蕴涵f(n)=\theta(h(n))$$<br>$$f(n)=O(g(n))且g(n)=O(h(n))，蕴涵f(n)=O(h(n))$$<br>$$f(n)=\Omega(g(n))且g(n)=\Omega(h(n))，蕴涵f(n)=\Omega(h(n))$$<br>$$f(n)=o(g(n))且g(n)=o(h(n))，蕴涵f(n)=o(h(n))$$<br>$$f(n)=\omega(g(n))且g(n)=\omega(h(n))，蕴涵f(n)=\omega(h(n))$$</p>
<h2 id="自反性"><a href="#自反性" class="headerlink" title="自反性"></a>自反性</h2><p>$$f(n)=\theta(f(n))$$<br>$$f(n)=O(f(n))$$<br>$$f(n)=\Omega(f(n))$$</p>
<h2 id="对称性"><a href="#对称性" class="headerlink" title="对称性"></a>对称性</h2><p>$$f(n)=\theta(g(n))当且仅当g(n)=\theta(f(n))$$</p>
<h2 id="转置对称性"><a href="#转置对称性" class="headerlink" title="转置对称性"></a>转置对称性</h2><p>$$f(n)=O(g(n))当且仅当g(n)=\Omega(f(n))$$<br>$$f(n)=o(g(n))当且仅当g(n)=\omega(f(n))$$</p>
<p>因为这些性质对渐近记号成立，所以可以在两个函数$f$和$g$的渐近比较和两个实数$a$和$b$的比较之间做一种类比。<br>$$f(n)=O(g(n))类似于a\leq b$$</p>
<p>$$f(n)=\Omega(g(n))类似于a\geq b$$</p>
<p>$$f(n)=\theta(g(n))类似于a=b$$</p>
<p>$$f(n)=o(g(n))类似于a&lt;b$$</p>
<p>$$f(n)=\omega(g(n))类似于a&gt;b$$</p>
<p>若$f(n)=o(g(n))$，则称$f(n)$<strong>渐近小于</strong>$g(n)$；若$f(n)=\omega(g(n))$，则称$f(n)$<strong>渐近大于</strong>$g(n)$。</p>
<p>然而，实数的下列性质不能携带到渐近记号：</p>
<p><strong>三分性</strong><br>对任意两个实数$a$和$b$，下列三种情况恰有一种必须成立：</p>
<p>$$①a&lt;b$$</p>
<p>$$②a=b$$</p>
<p>$$③a&gt;b$$</p>
<p>虽然任意两个实数都可以进行比较，但不是所有函数都可渐近比较。也就是说，对两个函数$f(n)$和$g(n)$，也许$f(n)=O(g(n))$和$f(n)=\Omega(g(n))$都不成立。例如，函数$n$和$n^{1+\sin n}$不能使用渐近记号比较，因为$n^{1+\sin n}$的指数在0与2之间摆动，取介于两者之间的所有值。</p>

      
    </div>

    <div>
      
        

      
    </div>

    <div>
      
        

      
    </div>

    <div>
      
        

      
    </div>

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/pages/tags/算法/" rel="tag"># 算法</a>
          
            <a href="/pages/tags/时间复杂度/" rel="tag"># 时间复杂度</a>
          
        </div>
      

      
        
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/pages/2017/04/20/算导笔记/二维最大子数组问题/index/" rel="next" title="二维最大子数组问题">
                <i class="fa fa-chevron-left"></i> 二维最大子数组问题
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/pages/2017/04/18/算导笔记/归并排序的应用——求逆序对数量/index/" rel="prev" title="归并排序应用——求逆序对数量">
                归并排序应用——求逆序对数量 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          
  <div class="comments" id="comments">
    
  </div>


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/pages/images/avatar.gif"
               alt="JROier" />
          <p class="site-author-name" itemprop="name">JROier</p>
           
              <p class="site-description motion-element" itemprop="description"></p>
          
        </div>
        <nav class="site-state motion-element">

          
            <div class="site-state-item site-state-posts">
              <a href="/pages/archives">
                <span class="site-state-item-count">7</span>
                <span class="site-state-item-name">日志</span>
              </a>
            </div>
          

          
            
            
            <div class="site-state-item site-state-categories">
              <a href="/pages/categories/index.html">
                <span class="site-state-item-count">1</span>
                <span class="site-state-item-name">分类</span>
              </a>
            </div>
          

          
            
            
            <div class="site-state-item site-state-tags">
              <a href="/pages/tags/index.html">
                <span class="site-state-item-count">4</span>
                <span class="site-state-item-name">标签</span>
              </a>
            </div>
          

        </nav>

        

        <div class="links-of-author motion-element">
          
        </div>

        
        

        
        

        


      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#什么是时间复杂度"><span class="nav-number">1.</span> <span class="nav-text">什么是时间复杂度</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#渐进记号"><span class="nav-number">2.</span> <span class="nav-text">渐进记号</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#theta-记号"><span class="nav-number">2.1.</span> <span class="nav-text">$\theta$记号</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#theta-记号的定义"><span class="nav-number">2.1.1.</span> <span class="nav-text">$\theta$记号的定义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#theta-记号的使用"><span class="nav-number">2.1.2.</span> <span class="nav-text">$\theta$记号的使用</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#theta-记号的几何意义"><span class="nav-number">2.1.3.</span> <span class="nav-text">$\theta$记号的几何意义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#渐近非负"><span class="nav-number">2.1.4.</span> <span class="nav-text">渐近非负</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#theta-记号的非形式化概念"><span class="nav-number">2.1.5.</span> <span class="nav-text">$\theta$记号的非形式化概念</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#O-记号"><span class="nav-number">2.2.</span> <span class="nav-text">$O$记号</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#O-记号的定义"><span class="nav-number">2.2.1.</span> <span class="nav-text">$O$记号的定义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#O-记号的使用"><span class="nav-number">2.2.2.</span> <span class="nav-text">$O$记号的使用</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#O-记号的几何意义"><span class="nav-number">2.2.3.</span> <span class="nav-text">$O$记号的几何意义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#O-记号的非形式化概念"><span class="nav-number">2.2.4.</span> <span class="nav-text">$O$记号的非形式化概念</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Omega-记号"><span class="nav-number">2.3.</span> <span class="nav-text">$\Omega$记号</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Omega-记号的定义"><span class="nav-number">2.3.1.</span> <span class="nav-text">$\Omega$记号的定义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Omega-记号的使用"><span class="nav-number">2.3.2.</span> <span class="nav-text">$\Omega$记号的使用</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Omega-记号的几何意义"><span class="nav-number">2.3.3.</span> <span class="nav-text">$\Omega$记号的几何意义</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#o-记号"><span class="nav-number">2.4.</span> <span class="nav-text">$o$记号</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#o-记号的定义"><span class="nav-number">2.4.1.</span> <span class="nav-text">$o$记号的定义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#o-记号的意义"><span class="nav-number">2.4.2.</span> <span class="nav-text">$o$记号的意义</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#omega-记号"><span class="nav-number">2.5.</span> <span class="nav-text">$\omega$记号</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#omega-记号的定义"><span class="nav-number">2.5.1.</span> <span class="nav-text">$\omega$记号的定义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#omega-记号的意义"><span class="nav-number">2.5.2.</span> <span class="nav-text">$\omega$记号的意义</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#等式及不等式中的渐进记号"><span class="nav-number">3.</span> <span class="nav-text">等式及不等式中的渐进记号</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#比较各种函数"><span class="nav-number">4.</span> <span class="nav-text">比较各种函数</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#传递性"><span class="nav-number">4.1.</span> <span class="nav-text">传递性</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#自反性"><span class="nav-number">4.2.</span> <span class="nav-text">自反性</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#对称性"><span class="nav-number">4.3.</span> <span class="nav-text">对称性</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#转置对称性"><span class="nav-number">4.4.</span> <span class="nav-text">转置对称性</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy; 
  <span itemprop="copyrightYear">2017</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">JROier</span>
</div>


<div class="powered-by">
  由 <a class="theme-link" href="https://hexo.io">Hexo</a> 强力驱动
</div>

<div class="theme-info">
  主题 -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Pisces
  </a>
</div>


        

        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  








  
  <script type="text/javascript" src="/pages/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/pages/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/pages/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/pages/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/pages/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/pages/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/pages/js/src/utils.js?v=5.1.0"></script>

  <script type="text/javascript" src="/pages/js/src/motion.js?v=5.1.0"></script>



  
  


  <script type="text/javascript" src="/pages/js/src/affix.js?v=5.1.0"></script>

  <script type="text/javascript" src="/pages/js/src/schemes/pisces.js?v=5.1.0"></script>



  
  <script type="text/javascript" src="/pages/js/src/scrollspy.js?v=5.1.0"></script>
<script type="text/javascript" src="/pages/js/src/post-details.js?v=5.1.0"></script>



  


  <script type="text/javascript" src="/pages/js/src/bootstrap.js?v=5.1.0"></script>



  


  




	





  





  





  






  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length == 0) {
      search_path = "search.xml";
    }
    var path = "/pages/" + search_path;
    // monitor main search box;

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.popup').toggle();
    }
    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';
      $.ajax({
        url: path,
        dataType: "xml",
        async: true,
        success: function( xmlResponse ) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = $( "entry", xmlResponse ).map(function() {
            return {
              title: $( "title", this ).text(),
              content: $("content",this).text(),
              url: $( "url" , this).text()
            };
          }).get();
          var $input = document.getElementById(search_id);
          var $resultContent = document.getElementById(content_id);
          $input.addEventListener('input', function(){
            var matchcounts = 0;
            var str='<ul class=\"search-result-list\">';
            var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
            $resultContent.innerHTML = "";
            if (this.value.trim().length > 1) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var content_index = [];
                var data_title = data.title.trim().toLowerCase();
                var data_content = data.content.trim().replace(/<[^>]+>/g,"").toLowerCase();
                var data_url = decodeURIComponent(data.url);
                var index_title = -1;
                var index_content = -1;
                var first_occur = -1;
                // only match artiles with not empty titles and contents
                if(data_title != '') {
                  keywords.forEach(function(keyword, i) {
                    index_title = data_title.indexOf(keyword);
                    index_content = data_content.indexOf(keyword);
                    if( index_title >= 0 || index_content >= 0 ){
                      isMatch = true;
                      if (i == 0) {
                        first_occur = index_content;
                      }
                    }

                  });
                }
                // show search results
                if (isMatch) {
                  matchcounts += 1;
                  str += "<li><a href='"+ data_url +"' class='search-result-title'>"+ data_title +"</a>";
                  var content = data.content.trim().replace(/<[^>]+>/g,"");
                  if (first_occur >= 0) {
                    // cut out 100 characters
                    var start = first_occur - 20;
                    var end = first_occur + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if(start == 0){
                      end = 50;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    var match_content = content.substring(start, end);
                    // highlight all keywords
                    keywords.forEach(function(keyword){
                      var regS = new RegExp(keyword, "gi");
                      match_content = match_content.replace(regS, "<b class=\"search-keyword\">"+keyword+"</b>");
                    });

                    str += "<p class=\"search-result\">" + match_content +"...</p>"
                  }
                  str += "</li>";
                }
              })};
            str += "</ul>";
            if (matchcounts == 0) { str = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>' }
            if (keywords == "") { str = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>' }
            $resultContent.innerHTML = str;
          });
          proceedsearch();
        }
      });}

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched == false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(function(e){
      $('.popup').hide();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    });
    $('.popup').click(function(e){
      e.stopPropagation();
    });
  </script>





  

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
